From b37b5de2e0041f77321fb73f4e925b50e135713a Mon Sep 17 00:00:00 2001 From: "iap10@labyrinth.cl.cam.ac.uk" Date: Fri, 4 Feb 2005 22:47:58 +0000 Subject: [PATCH] bitkeeper revision 1.1159.242.1 (4203fb9erjxo9v5Lwlohe2bcTrLYpg) 1. Deleted slab.c, added xmalloc.c. Do not rename header or remove unnecessary includes (yet). 2. Add explicit align arg, although current implementation over-aligns. 3. Add list_for_each_entry_safe(). 4. Make xmalloc_array use _xmalloc_array, to avoid duplicate eval of "num" arg. 5. Rearrange slab.h a little to show the exposed functions/macros first. Signed-off-by: Rusty Russell Signed-off-by: ian.pratt@cl.cam.ac.uk --- .rootkeys | 1 + xen/arch/x86/setup.c | 4 - xen/common/page_alloc.c | 10 +-- xen/common/xmalloc.c | 170 +++++++++++++++++++++++++++++++++++++++ xen/include/xen/domain.h | 2 - xen/include/xen/list.h | 12 +++ xen/include/xen/slab.h | 56 ++++--------- 7 files changed, 200 insertions(+), 55 deletions(-) create mode 100644 xen/common/xmalloc.c diff --git a/.rootkeys b/.rootkeys index f331481b60..33451dc335 100644 --- a/.rootkeys +++ b/.rootkeys @@ -940,6 +940,7 @@ 3e7f358awXBC3Vw-wFRwPw18qL1khg xen/common/string.c 403a3edbejm33XLTGMuinKEwQBrOIg xen/common/trace.c 3ddb79bd3zgV33PHdt-cgh3sxcb1hw xen/common/vsprintf.c +4203fb92Qcy7mGpauBdq09J-WAqfoA xen/common/xmalloc.c 3ddb79c0ppNeJtjC4va8j41ADCnchA xen/drivers/Makefile 40715b2bi9gU43-cYzlmPDgreYQchw xen/drivers/acpi/Makefile 40715b2bDxNCz5LFV8FAXihmYJZFUQ xen/drivers/acpi/acpi_ksyms.c diff --git a/xen/arch/x86/setup.c b/xen/arch/x86/setup.c index cdbbcf3db2..409e825d23 100644 --- a/xen/arch/x86/setup.c +++ b/xen/arch/x86/setup.c @@ -594,10 +594,6 @@ void __init __start_xen(multiboot_info_t *mbi) early_boot = 0; - /* Initialise the slab allocator. */ - xmem_cache_init(); - xmem_cache_sizes_init(max_page); - start_of_day(); grant_table_init(); diff --git a/xen/common/page_alloc.c b/xen/common/page_alloc.c index 84ee8d57fd..8afa482da1 100644 --- a/xen/common/page_alloc.c +++ b/xen/common/page_alloc.c @@ -403,9 +403,8 @@ unsigned long alloc_xenheap_pages(unsigned int order) { unsigned long flags; struct pfn_info *pg; - int i, attempts = 0; + int i; - retry: local_irq_save(flags); pg = alloc_heap_pages(MEMZONE_XEN, order); local_irq_restore(flags); @@ -425,14 +424,7 @@ unsigned long alloc_xenheap_pages(unsigned int order) return (unsigned long)page_to_virt(pg); no_memory: - if ( attempts++ < 8 ) - { - xmem_cache_reap(); - goto retry; - } - printk("Cannot handle page request order %d!\n", order); - dump_slabinfo(); return 0; } diff --git a/xen/common/xmalloc.c b/xen/common/xmalloc.c new file mode 100644 index 0000000000..68c1db8345 --- /dev/null +++ b/xen/common/xmalloc.c @@ -0,0 +1,170 @@ +/* Simple allocator for Xen. If larger than a page, simply use the + * page-order allocator. + * + * Copyright (C) 2005 Rusty Russell IBM Corporation + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ +#include +#include +#include +#include + +#define BUG_ON(x) do { if (x) BUG(); }while(0) + +static LIST_HEAD(freelist); +static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED; + +struct xmalloc_hdr +{ + /* Total including this hdr. */ + size_t size; + struct list_head freelist; +} __attribute__((__aligned__(SMP_CACHE_BYTES))); + +static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block) +{ + size_t leftover = block - size; + + /* If enough left to make a block, put it on free list. */ + if (leftover >= sizeof(struct xmalloc_hdr)) { + struct xmalloc_hdr *extra; + + extra = (void *)hdr + size; + extra->size = leftover; + list_add(&extra->freelist, &freelist); + } else + size = block; + + hdr->size = size; + /* Debugging aid. */ + hdr->freelist.next = hdr->freelist.prev = NULL; +} + +static void *xmalloc_new_page(size_t size) +{ + struct xmalloc_hdr *hdr; + unsigned long flags; + + hdr = (void *)alloc_xenheap_pages(0); + if (!hdr) + return NULL; + + spin_lock_irqsave(&freelist_lock, flags); + maybe_split(hdr, size, PAGE_SIZE); + spin_unlock_irqrestore(&freelist_lock, flags); + return hdr+1; +} + +/* Big object? Just use page allocator. */ +static void *xmalloc_whole_pages(size_t size) +{ + struct xmalloc_hdr *hdr; + unsigned int pageorder = get_order(size); + + hdr = (void *)alloc_xenheap_pages(pageorder); + if (!hdr) + return NULL; + + hdr->size = (1 << (pageorder + PAGE_SHIFT)); + /* Debugging aid. */ + hdr->freelist.next = hdr->freelist.prev = NULL; + return hdr+1; +} + +/* Return size, increased to alignment with align. */ +static inline size_t align_up(size_t size, size_t align) +{ + return (size + align-1) & ~(align - 1); +} + +void *_xmalloc(size_t size, size_t align) +{ + struct xmalloc_hdr *i; + unsigned long flags; + + /* We currently always return cacheline aligned. */ + BUG_ON(align > SMP_CACHE_BYTES); + + /* Add room for header, pad to align next header. */ + size += sizeof(struct xmalloc_hdr); + size = align_up(size, __alignof__(struct xmalloc_hdr)); + + /* For big allocs, give them whole pages. */ + if (size >= PAGE_SIZE) + return xmalloc_whole_pages(size); + + /* Search free list */ + spin_lock_irqsave(&freelist_lock, flags); + list_for_each_entry(i, &freelist, freelist) { + if (i->size >= size) { + list_del(&i->freelist); + maybe_split(i, size, i->size); + spin_unlock_irqrestore(&freelist_lock, flags); + return i+1; + } + } + spin_unlock_irqrestore(&freelist_lock, flags); + + /* Alloc a new page and return from that. */ + return xmalloc_new_page(size); +} + +void xfree(const void *p) +{ + unsigned long flags; + struct xmalloc_hdr *i, *tmp, *hdr; + + if (!p) + return; + + hdr = (struct xmalloc_hdr *)p - 1; + + /* We know hdr will be on same page. */ + BUG_ON(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK)); + + /* Not previously freed. */ + BUG_ON(hdr->freelist.next || hdr->freelist.prev); + + /* Big allocs free directly. */ + if (hdr->size >= PAGE_SIZE) { + free_xenheap_pages((unsigned long)hdr, get_order(hdr->size)); + return; + } + + /* Merge with other free block, or put in list. */ + spin_lock_irqsave(&freelist_lock, flags); + list_for_each_entry_safe(i, tmp, &freelist, freelist) { + /* We follow this block? Swallow it. */ + if ((void *)i + i->size == (void *)hdr) { + list_del(&i->freelist); + i->size += hdr->size; + hdr = i; + } + /* It follows us? Delete it and add it to us. */ + if ((void *)hdr + hdr->size == (void *)i) { + list_del(&i->freelist); + hdr->size += i->size; + } + } + + /* Did we free entire page? */ + if (hdr->size == PAGE_SIZE) { + BUG_ON((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0); + free_xenheap_pages((unsigned long)hdr, 0); + } else + list_add(&hdr->freelist, &freelist); + spin_unlock_irqrestore(&freelist_lock, flags); +} diff --git a/xen/include/xen/domain.h b/xen/include/xen/domain.h index c2d0dbc144..d502f18871 100644 --- a/xen/include/xen/domain.h +++ b/xen/include/xen/domain.h @@ -6,8 +6,6 @@ * Arch-specifics. */ -extern void domain_startofday(void); - extern struct domain *arch_alloc_domain_struct(void); extern void arch_free_domain_struct(struct domain *d); diff --git a/xen/include/xen/list.h b/xen/include/xen/list.h index 7b19bb4650..93d9f987e7 100644 --- a/xen/include/xen/list.h +++ b/xen/include/xen/list.h @@ -174,5 +174,17 @@ static __inline__ void list_splice(struct list_head *list, struct list_head *hea pos = list_entry(pos->member.next, typeof(*pos), member), \ prefetch(pos->member.next)) +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) #endif /* _LINUX_LIST_H */ diff --git a/xen/include/xen/slab.h b/xen/include/xen/slab.h index d340651bac..8e510d4a3b 100644 --- a/xen/include/xen/slab.h +++ b/xen/include/xen/slab.h @@ -14,55 +14,31 @@ #else -typedef struct xmem_cache_s xmem_cache_t; - #include #include #include -/* Flags to pass to xmem_cache_create(). */ -/* NB. The first 3 are only valid when built with SLAB_DEBUG_SUPPORT. */ -#define SLAB_DEBUG_INITIAL 0x00000200UL /* Call constructor */ -#define SLAB_RED_ZONE 0x00000400UL /* Red zone objs in a cache */ -#define SLAB_POISON 0x00000800UL /* Poison objects */ -#define SLAB_NO_REAP 0x00001000UL /* never reap from the cache */ -#define SLAB_HWCACHE_ALIGN 0x00002000UL /* align obj on a cache line */ - -/* Flags passed to a constructor function. */ -#define SLAB_CTOR_CONSTRUCTOR 0x001UL /* if not set, then deconstructor */ -#define SLAB_CTOR_ATOMIC 0x002UL /* tell cons. it can't sleep */ -#define SLAB_CTOR_VERIFY 0x004UL /* tell cons. it's a verify call */ - -extern void xmem_cache_init(void); -extern void xmem_cache_sizes_init(unsigned long); - -extern xmem_cache_t *xmem_find_general_cachep(size_t); -extern xmem_cache_t *xmem_cache_create( - const char *, size_t, size_t, unsigned long, - void (*)(void *, xmem_cache_t *, unsigned long), - void (*)(void *, xmem_cache_t *, unsigned long)); -extern int xmem_cache_destroy(xmem_cache_t *); -extern int xmem_cache_shrink(xmem_cache_t *); -extern void *xmem_cache_alloc(xmem_cache_t *); -extern void xmem_cache_free(xmem_cache_t *, void *); - -extern void *_xmalloc(size_t); -extern void xfree(const void *); - -extern int xmem_cache_reap(void); - -extern void dump_slabinfo(); - /* Allocate space for typed object. */ -#define xmalloc(_type) ((_type *)_xmalloc(sizeof(_type))) +#define xmalloc(_type) ((_type *)_xmalloc(sizeof(_type), __alignof__(_type))) /* Allocate space for array of typed objects. */ -#define xmalloc_array(_type, _num) \ -((_type *)(((_num) > (UINT_MAX / sizeof(_type))) ? \ - NULL : _xmalloc((_num) * sizeof(_type)))) +#define xmalloc_array(_type, _num) ((_type *)_xmalloc_array(sizeof(_type), __alignof__(_type), _num)) /* Allocate untyped storage. */ -#define xmalloc_bytes(_bytes) (_xmalloc(_bytes)) +#define xmalloc_bytes(_bytes) (_xmalloc(_bytes, SMP_CACHE_BYTES)) + +/* Free any of the above. */ +extern void xfree(const void *); + +/* Underlying functions */ +extern void *_xmalloc(size_t size, size_t align); +static inline void *_xmalloc_array(size_t size, size_t align, size_t num) +{ + /* Check for overflow. */ + if (size && num > UINT_MAX / size) + return NULL; + return _xmalloc(size * num, align); +} #endif /* __ARCH_HAS_SLAB_ALLOCATOR */ -- 2.30.2